[NOI Online]sequence

2020-03-07
#图论 #缩点 #染色
NOI-Online

题意

给出序列$\{a_i\}$，要求经过一些操作，变成序列$\{b_i\}$，两序列保证长度相同

有$m$种操作，操作把$a_u,a_v$同加或减1，操作2把$a_u,a_v$一个加1一个减1

每种操作可以使用无数次，问是否能成功，$n,m\leq 10^5​$

题解

先考虑操作2，发现被操作2连成的联通块里面数值可以随意流通，这样就可以缩点了

再考虑操作1，对缩完点后的图每个联通块黑白染色

对于某个联通块而言，如果和为奇数就NO；否则如果可以黑白染色，黑节点和白节点和不同也NO

所有联通块都YES，就YES

调试记录

没判奇环的和的奇偶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#define LL long long
const int maxn = 1e6 + 5;
using namespace std;
int n, m, a[maxn], b[maxn], u[maxn], v[maxn], Etot;
int f[maxn], c[maxn], Ctot;
int getf(int x){
	return x == f[x] ? x : f[x] = getf(f[x]);
}
struct E{
	int to, nxt;
}e[maxn << 1];
int head[maxn], tot = 0;
void addedge(int u, int v){
	e[++tot].to = v, e[tot].nxt = head[u];
	head[u] = tot;
} LL val[maxn], sum; bool res, pass;
void dfs(int cur, int C){
	c[cur] = C; sum += val[cur] * C; 
	for (int i = head[cur]; i; i = e[i].nxt){
		int v = e[i].to;
		if (c[v] == 0) dfs(v, -C);
		else if (c[v] == C) res &= 1, pass = 1;
	}
}
inline int read(){
	int x = 0; char ch = getchar();
	while (!isdigit(ch)) ch = getchar();
	while (isdigit(ch)) x = (x * 10) + (ch & 15), ch = getchar();
	return x;
}
int main(){
//	freopen("sequence.in", "r", stdin);
//	freopen("sequence.out", "w", stdout);
	int T; scanf("%d", &T);
	while (T--){
		n = read(), m = read(); Ctot = 0; Etot = 0;
		for (int i = 1; i <= n; i++) a[i] = read();
		for (int i = 1; i <= n; i++) b[i] = read();
		for (int i = 1; i <= n; i++) a[i] -= b[i], b[i] = 0, f[i] = i;
		
//		memset(c, 0, sizeof c); memset(val, 0, sizeof val); 
		for (int opt, x, y, i = 1; i <= m; i++){
			opt = read(), x = read(), y = read();
			if (opt == 1) u[++Etot] = x, v[Etot] = y;
			if (opt == 2) f[getf(x)] = getf(y);
		}
		for (int i = 1; i <= n; i++){
			if (!c[getf(i)]) c[getf(i)] = ++Ctot;
			c[i] = c[getf(i)]; val[c[getf(i)]] += 1ll * a[i];
		}
//		memset(head, 0, sizeof head); tot = 0;
		for (int i = 1; i <= Etot; i++)
			addedge(c[u[i]], c[v[i]]), addedge(c[v[i]], c[u[i]]);
		
//		memset(c, 0, sizeof c);
		for (int i = 1; i <= n; i++) c[i] = 0;
		res = 1;
		for (int i = 1; i <= Ctot; i++){
			sum = 0;
			if (c[i] == 0) pass = 0, dfs(i, 1);
			if (sum % 2 != 0) res &= 0; 
			if (pass) continue;
			if (sum == 0) res &= 1;
			else res &= 0;
			pass = 1;
		}
		if (res) puts("YES");
		else puts("NO");
		for (int i = 1; i <= n; i++) c[i] = 0, val[i] = 0;
		for (int i = 1; i <= n; i++) head[i] = 0; tot = 0;
	}
	return 0;
}